//: C20:SequencePerformance.cpp
// From Thinking in C++, 2nd Edition
// Available at http://www.BruceEckel.com
// (c) Bruce Eckel 1999
// Copyright notice in Copyright.txt
// Comparing the performance of the basic
// sequence containers for various operations
#include <vector>
#include <queue>
#include <list>
#include <iostream>
#include <string>
#include <typeinfo>
#include <ctime>
#include <cstdlib>
using namespace std;

class FixedSize
{
    int x[20];
    // Automatic generation of default constructor,
    // copy-constructor and operator=
} fs;

template<class Cont>
struct InsertBack {
    void operator()(Cont& c, long count) {
        for (long i = 0; i < count; i++)
            c.push_back(fs);
    }
    char* testName() {
        return "InsertBack";
    }
};

template<class Cont>
struct InsertFront {
    void operator()(Cont& c, long count) {
        long cnt = count * 10;
        for (long i = 0; i < cnt; i++)
            c.push_front(fs);
    }
    char* testName() {
        return "InsertFront";
    }
};

template<class Cont>
struct InsertMiddle {
    void operator()(Cont& c, long count) {
        typename Cont::iterator it;
        long cnt = count / 10;
        for (long i = 0; i < cnt; i++) {
            // Must get the iterator every time to keep
            // from causing an access violation with
            // vector. Increment it to put it in the
            // middle of the container:
            it = c.begin();
            it++;
            c.insert(it, fs);
        }
    }
    char* testName() {
        return "InsertMiddle";
    }
};

template<class Cont>
struct RandomAccess { // Not for list
    void operator()(Cont& c, long count) {
        int sz = c.size();
        long cnt = count * 100;
        for (long i = 0; i < cnt; i++)
            c[rand() % sz];
    }
    char* testName() {
        return "RandomAccess";
    }
};

template<class Cont>
struct Traversal {
    void operator()(Cont& c, long count) {
        long cnt = count / 100;
        for (long i = 0; i < cnt; i++) {
            typename Cont::iterator it = c.begin(),
                                         end = c.end();
            while (it != end) it++;
        }
    }
    char* testName() {
        return "Traversal";
    }
};

template<class Cont>
struct Swap {
    void operator()(Cont& c, long count) {
        int middle = c.size() / 2;
        typename Cont::iterator it = c.begin(),
                                     mid = c.begin();
        it++; // Put it in the middle
        for (int x = 0; x < middle + 1; x++)
            mid++;
        long cnt = count * 10;
        for (long i = 0; i < cnt; i++)
            swap(*it, *mid);
    }
    char* testName() {
        return "Swap";
    }
};

template<class Cont>
struct RemoveMiddle {
    void operator()(Cont& c, long count) {
        long cnt = count / 10;
        if (cnt > c.size()) {
            cout << "RemoveMiddle: not enough elements"
                 << endl;
            return;
        }
        for (long i = 0; i < cnt; i++) {
            typename Cont::iterator it = c.begin();
            it++;
            c.erase(it);
        }
    }
    char* testName() {
        return "RemoveMiddle";
    }
};

template<class Cont>
struct RemoveBack {
    void operator()(Cont& c, long count) {
        long cnt = count * 10;
        if (cnt > c.size()) {
            cout << "RemoveBack: not enough elements"
                 << endl;
            return;
        }
        for (long i = 0; i < cnt; i++)
            c.pop_back();
    }
    char* testName() {
        return "RemoveBack";
    }
};

template<class Op, class Container>
void measureTime(Op f, Container& c, long count)
{
    string id(typeid(f).name());
    bool Deque = id.find("deque") != string::npos;
    bool List = id.find("list") != string::npos;
    bool Vector = id.find("vector") !=string::npos;
    string cont = Deque ? "deque" : List ? "list"
                  : Vector? "vector" : "unknown";
    cout << f.testName() << " for " << cont << ": ";
    // Standard C library CPU ticks:
    clock_t ticks = clock();
    f(c, count); // Run the test
    ticks = clock() - ticks;
    cout << ticks << endl;
}

typedef deque<FixedSize> DF;
typedef list<FixedSize> LF;
typedef vector<FixedSize> VF;

int main(int argc, char* argv[])
{
    srand(time(0));
    long count = 1000;
    if (argc >= 2) count = atoi(argv[1]);
    DF deq;
    LF lst;
    VF vec, vecres;
    vecres.reserve(count); // Preallocate storage
    measureTime(InsertBack<VF>(), vec, count);
    measureTime(InsertBack<VF>(), vecres, count);
    measureTime(InsertBack<DF>(), deq, count);
    measureTime(InsertBack<LF>(), lst, count);
    // Can't push_front() with a vector:
//! measureTime(InsertFront<VF>(), vec, count);
    measureTime(InsertFront<DF>(), deq, count);
    measureTime(InsertFront<LF>(), lst, count);
    measureTime(InsertMiddle<VF>(), vec, count);
    measureTime(InsertMiddle<DF>(), deq, count);
    measureTime(InsertMiddle<LF>(), lst, count);
    measureTime(RandomAccess<VF>(), vec, count);
    measureTime(RandomAccess<DF>(), deq, count);
    // Can't operator[] with a list:
//! measureTime(RandomAccess<LF>(), lst, count);
    measureTime(Traversal<VF>(), vec, count);
    measureTime(Traversal<DF>(), deq, count);
    measureTime(Traversal<LF>(), lst, count);
    measureTime(Swap<VF>(), vec, count);
    measureTime(Swap<DF>(), deq, count);
    measureTime(Swap<LF>(), lst, count);
    measureTime(RemoveMiddle<VF>(), vec, count);
    measureTime(RemoveMiddle<DF>(), deq, count);
    measureTime(RemoveMiddle<LF>(), lst, count);
    vec.resize(vec.size() * 10); // Make it bigger
    measureTime(RemoveBack<VF>(), vec, count);
    measureTime(RemoveBack<DF>(), deq, count);
    measureTime(RemoveBack<LF>(), lst, count);
} ///:~
